package com.liufei.class07;

import com.liufei.common.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

public class Code02_BalancedBinaryTree {


    public static class Info {
        boolean isBST;
        int min;
        int max;

        public Info() {
        }

        public Info(boolean isBST, int min, int max) {
            this.isBST = isBST;
            this.min = min;
            this.max = max;
        }
    }

    public static boolean isValidBST(TreeNode root) {
        return process(root).isBST;
    }


    // https://leetcode.cn/problems/validate-binary-search-tree/description/
    public static Info process(TreeNode root) {
        if (root == null) {
            // 这里返回null的时候，后续要做空判断
            return null;
        }
        Info leftInfo = process(root.left);
        Info rightInfo = process(root.right);
        int min = root.val;
        int max = root.val;

        if (leftInfo != null) {
            min = Math.min(min, leftInfo.min);
            max = Math.max(max, leftInfo.max);
        }

        if (rightInfo != null) {
            min = Math.min(min, rightInfo.min);
            max = Math.max(max, rightInfo.max);
        }

        boolean isBST = true;

        if (leftInfo != null && !leftInfo.isBST) {
            isBST = false;
        }

        if (rightInfo != null && !rightInfo.isBST) {
            isBST = false;
        }

        // 左边最大值 < x && 右边最小值 > x 就是平衡二叉树
        boolean leftMaxLessX = leftInfo == null ? true : leftInfo.max < root.val;
        boolean rightMinMoreX = rightInfo == null ? true : rightInfo.min > root.val;
        if (!(leftMaxLessX && rightMinMoreX)) {
            isBST = false;
        }
        return new Info(isBST, min, max);
    }

    public static class BalanceInfo {
        boolean isBalanced;

        int depth;

        public BalanceInfo() {
        }
        public BalanceInfo(boolean isBalanced, int maxLevel, int depth) {
            this.isBalanced = isBalanced;
            this.depth = maxLevel;
        }
    }


    // https://leetcode.cn/problems/balanced-binary-tree/
    public static boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        } else {
            return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
    }

    public static int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(height(root.left), height(root.right)) + 1;
    }

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node21 = new TreeNode(2);
        TreeNode node22 = new TreeNode(2);
        node1.left = node21;
        node1.right = node22;

        TreeNode node31 = new TreeNode(3);
        TreeNode node32 = new TreeNode(3);

        node21.left = node31;
        node21.right = node32;

        TreeNode node41 = new TreeNode(4);
        TreeNode node42 = new TreeNode(4);
        node31.left = node41;
        node31.right = node42;

        isBalanced(node1);
    }
}
